1. Field of the Invention
The present invention relates to a technique of starting execution of threads simultaneously at a plurality of processors at the time of thread context switching in a multi-processor system and, more particularly, to a technique of handling a plurality of thread execution states at a plurality of processors, that is, a plurality of thread contexts, as a single unit.
2. Description of the Related Art
As an example of a conventional kernel scheduler at a plurality of processors, handling of threads in Solaris is recited in xe2x80x9cUresh Vahalia: UNIX Internals The New Frontiers, Prentice Hall, pp. 130-139, 1996xe2x80x9d and xe2x80x9cBill Luis and Daniel Berk: Guidance to Multi-thread Programming, ASCII Publishing, pp. 73-77, September 1996xe2x80x9d. Unit for exclusive control among a plurality of processors is described in xe2x80x9cA. S. Tanenbaum: Basics and Application of OS, Prentice Hall Toppan Company, 2nd chapter, 2nd paragraph. An example of a multi-processor system which executes a plurality of generated tasks in parallel to each other is recited in Japanese Patent Laying-Open (Kokai) No. Heisei 9-319653.
As shown in FIG. 9, structure of the conventional kernel scheduler having the minimum number of processors includes an input device 1, a first processor 27, a second processor 28, an inter-processor interruption notification device 29, a main storage 3 and an output device 4.
Further included are in the first processor 27, an exception management device 271, and an interruption processing unit 272 and a kernel scheduler unit 273 executed by the first processor 27, in the second processor 28, an exception management device 281, and an interruption processing unit 282 and a kernel scheduler unit 283 executed by the second processor 28, and on the main storage 3, an exclusive control variable 31, a context save area 32, a dispatch queue 33 and a priority list 38.
FIG. 10 is a flow chart showing operation of the interruption processing units 272 and 282 and the kernel scheduler units 273 and 283 of FIG. 9.
Operation of thus structured conventional kernel scheduler will be described in the following with reference to FIGS. 9 and 10.
Assume that a processor which receives an exception applied through the input device 1 is the first processor 27, a first exception factor 11 is received by the exception management device 271 of the first processor 27 to activate the interruption processing unit 272 (Step S1).
In the interruption processing unit 272, a context save unit 2723 is called and an execution state of the first processor 27, that is, a context, is saved, assuming that a currently executed thread is the first thread, as a context 321 of the first thread in the context save area 32 (Step S2).
The interruption processing unit 272 subsequently activates the kernel scheduler unit 273, where an exclusive arbitration unit 2731 is first executed. If the second processor 28 has changed the exclusive control variable 31, the unit 2731 waits (Step S3) and otherwise, rewrites the exclusive control variable 31 to prevent other processors from accessing an area of the dispatch queue 33 or the like necessary for the subsequent operation (Steps S4 and S5).
Subsequently, a dispatch queue operation unit 2732 in the kernel scheduler unit 273 determines whether there exists a thread newly attaining an executable state by the first exception factor 11 and the processing by the interruption processing unit 272 (Step S6) and when the thread exists, the unit 2732 registers a structure or an ID number indicative of the thread at the dispatch queue 33 (Step S7). The example of FIG. 9 shows a state where the first processor 27 registers a structure 333 indicative of a third thread as a priority xe2x80x9c115xe2x80x9d. It is assumed here that the larger the value is, the higher the priority is.
Furthermore, an object to be activated selection unit 2733 searches the threads waiting at the dispatch queue 33 for a thread having the highest priority (Step S8) and searches the priority list 38 for a processor whose executing thread has the lowest priority (Step S9). In the example of FIG. 9, this search obtains the third thread having the priority xe2x80x9c115xe2x80x9d from the dispatch queue 33 and the second processor being executing the priority xe2x80x9c100xe2x80x9d from the priority list 38.
Next, the object to be activated selection unit 2733 determines whether the priority xe2x80x9c115xe2x80x9d of the structure 333 indicative of the third thread which is the highest priority among the threads waiting at the dispatch queue 33 exceeds the priority xe2x80x9c100xe2x80x9d of the thread being executed by the second processor which is the lowest priority in the priority list 38 (Step S10). In this case, the former priority exceeds the latter, the unit 2733 further determines whether its own processor is executing the lowest priority thread or not (Step S11). In this case, the processor is not executing the thread in question. In such a case as this where a priority of a thread waiting at the dispatch queue 33 is higher than a priority of a thread being executed at other processor, an inter-processor interruption unit 2734 gives a notification to a processor which is executing the lowest priority thread by using an inter-processor interruption (Step S12). In the example of FIG. 9, the second processor 28 is to be notified.
The first processor 27, after giving a notification using an inter-processor interruption, releases exclusive conditions by restoring the exclusive control variable 31 to an original state (Step S15) and returns the context to move onto a state prior to generation of the first exception factor 11. In the example of FIG. 9, the processor will return to the original first thread.
On the other hand, at the processor 28 to be notified of an inter-processor interruption, the exception management device 281 of the second processor 28 is given a notification of an inter-processor interruption by the inter-processor interruption notification device 29 to activate the interruption processing unit 282.
In the interruption processing unit 282, similarly to the interruption processing unit 272 which has processed the first exception factor 11, a context save unit 2823 is called to save an execution state of the second processor, that is, a context of the second thread, as a context 322 of the second thread in the context save area 32 (Step S2).
The interruption processing unit 282 activates the kernel scheduler unit 283, where an exclusive arbitration unit 2831 is first executed. When other processor has changed the exclusive control variable 31 in such a case where processing of the kernel scheduler unit 273 at the first processor 27 is yet to be completed or the like, the unit 2831 waits (Step S3) and otherwise, the unit changes the exclusive control variable 31 to prevent other processors from accessing an area of the dispatch queue 33 or the like necessary for subsequent operation (Steps 4 and 5).
Subsequently, a dispatch queue operation unit 2832 in the kernel scheduler unit 283 determines whether there exists a thread newly attaining an executable state by the processing by the inter-processor interruption notification device 29 and the interruption processing unit 282 (Step S6) and when the thread exits, the unit 2832 additionally registers the context from the context save area 32 at the dispatch queue 33 (Step S7).
In the example of FIG. 9, it is assumed that there exists no thread which newly attains an executable state after the structure 333 indicative of the third thread is registered by the first processor 27.
Furthermore, an object to be activated selection unit 2833 searches the threads waiting at the dispatch queue 33 for a thread having the highest priority (Step S8) and also searches the priority list 38 for a processor whose executing thread has the lowest priority (Step S9). In the example of FIG. 9, this search obtains the third thread having the priority xe2x80x9c115xe2x80x9d from the dispatch queue 33 and the second processor which is executing the priority xe2x80x9c100xe2x80x9d from the priority list 38.
Next, the object to be activated selection unit 2833 determines whether the priority xe2x80x9c115xe2x80x9d, of the structure 333 indicative of the third thread which is the highest priority among the threads waiting at the dispatch queue 33 exceeds the priority xe2x80x9c100xe2x80x9d of the thread being executed by the second processor which is the lowest priority in the priority list 38 (Step S10). In this case, since the former priority exceeds the latter, the unit 2833 further determines whether its own processor is executing the lowest priority thread or not (Step S11). In this case, the processor is executing the thread in question. In such a case as this where a priority of a thread waiting at the dispatch queue 33 is higher than a priority of a thread being executed at other processor, the object to be activated selection unit 2833 selects the third thread having the highest priority among those waiting at the dispatch queue 33 as a context of a thread to be executed next (Step S13) and changes the priority of the thread being executed by its own processor in the priority list 38 into a priority of the next context (Step S14).
Lastly, the second processor 28 releases exclusive conditions by restoring the exclusive control variable 31 to an original state (Step S15) and reads the next context to move on to execution of a new thread, that is, the third thread.
As described above, in the conventional art, each kernel scheduler unit at each processor detects a thread to be executed next based on its priority and the kernel scheduler units are activated by means of an inter-processor interruption notification device, thereby realizing activation processing of a plurality of threads among a plurality of processors. Such conventional method has the following problems.
The first problem is that it is impossible to exactly determine to which thread and when a thread being executed by each processor is switched among the processors unless a synchronization unit is provided in addition to a kernel scheduler unit.
More specifically, in conventional art, a kernel scheduler unit operating at each processor operates basically independently of each other. The kernel scheduler unit is allowed to cope with a plurality of processors by adding, to a basic function of shifting execution when a priority accommodated in a thread structure on a dispatch queue is higher than a priority of a thread being executed, a function of requesting execution of a new thread by means of an inter-processor interruption notification device when there exists other processor whose executing thread has a lower priority and further adding an exclusive arbitration unit for preventing operation of the dispatch queue or the like from contending. Therefore, even when the kernel scheduler unit at a certain processor requests execution of a new thread from other processor, another high-priority thread might be registered at a dispatch queue at the requested processor, so that after making the request, the requesting-side processor needs to monitor which thread is actually activated at the requested processor by means of a synchronization unit provided in addition to the kernel scheduler unit.
When in the middle of the monitoring of the requested processor by the requesting-side processor, other processor makes a request to the requesting processor for activation of another thread, a thread having a priority to be executed might be kept waiting for a long time unless the requesting side processor accepts the request. It is accordingly a conventional practice that at the monitoring of a requested processor, a kernel scheduler unit at a requesting-side processor is completed to again conduct monitoring by other unit than the kernel scheduler unit at a state of receiving an inter-processor interruption request.
The second problem is that when operation of a thread executed at each processor is to be synchronized with each other, an overhead in synchronization processing is increased.
The reason is that for activating a thread to be synchronized, the above-described monitoring mechanism should be used in addition to the activation of a thread by a kernel scheduler unit in terms of the first problem.
An object of the present invention is therefore enabling execution of threads designated by a plurality of processors to be started simultaneously at the switching of threads executed among the respective processors.
Another object of the present invention is to manage a plurality of threads as one unit to enable execution of threads of the same unit to be started simultaneously at a plurality of processors.
According to the first aspect of the invention, in a multi-processor system in which a plurality of threads to be simultaneously executed at a plurality of processors are stored as one thread set at a context area one-to-one corresponding to a thread set provided in a context save area on a main storage, a method of enabling a plurality of processors to start execution of threads simultaneously, wherein
exclusive arbitration is conducted during exception processing so as to temporarily allow only one processor among the plurality of processors constituting the multi-processor system to obtain kernel scheduler execution authority, and
a processor obtaining kernel scheduler execution authority selects a thread set to be executed next and controls such that a plurality of threads in the selected thread set are executed simultaneously at a plurality of processors including its own processor.
In the preferred construction, at the exclusive arbitration, a processor failing to obtain kernel scheduler execution authority prepares and waits for reception of an inter-processor interruption from a processor obtaining kernel scheduler execution authority and when receiving an inter-processor interruption, sets such that an exception reoccurs after thread switching by returning exception generation conditions waiting to a state before the reception of the exception. In another preferred construction, after contexts of a plurality of threads in a thread set are read by the respective processors, arbitration is conducted by means of synchronization means to enable each processor to start thread execution simultaneously.
According to the second aspect of the invention, in a multi-processor system in which a plurality of threads to be simultaneously executed at a plurality of processors are stored as one thread set at a context area one-to-one corresponding to a thread set provided in a context save area on a main storage, a method of enabling a plurality of processors to start execution of threads simultaneously, comprising the steps:
(a) of conducting exclusive arbitration during exception processing of each processor so as to temporarily allow only one processor to obtain kernel scheduler execution authority,
(b) of a processor obtaining kernel scheduler execution authority to save a context of a thread being executed by its own processor in the context save area on the main storage, as well as issuing a context save request as an inter-processor interruption to a processor executing other thread in the thread set to which the thread in question belongs,
(c) of a processor issuing a context save request to, after confirming the completion of context saving at all of the requested processors, issue a context reading request regarding a thread to be executed by other processor in a thread set to be executed next to a processor which is to execute the thread in question, as well as reading a context of a thread to be executed by its own processor in the thread set to be executed next from the context save area on the main storage to return the context,
(d) of a processor receiving the context reading request to read a context of the thread to return the context, and
(e) upon completion of context return at all the processors executing threads in the thread set, of all the relevant processors to simultaneously start execution of threads.
In the preferred construction, the context save request is issued at Step (b) by designating a position in the context save area on the main storage. In another preferred construction, the method of enabling a plurality of processors to simultaneously start execution of threads in a multi-processor system further comprising the step of a processor receiving an inter-processor interruption related to the context save request to save a context of a thread being executed by its own processor in a designated position of the context save area on the main storage and notify a requesting-side processor of the completion.
In another preferred construction, a context reading request is made at Step (c) by designating a position of the context save area on the main storage which stores a context of a thread to be executed next.
In another preferred construction, a context is returned at Step (d) by reading a context of the thread from a designated position of the context save area on the main storage.
In another preferred construction, at Step (d), completion of context return is notified to all the processors executing threads in the thread set to which the thread in question belongs.
In another preferred construction, the method of enabling a plurality of processors to simultaneously start execution of threads in a multi-processor system further comprising the step, at the exclusive arbitration at Step (a), of a processor failing to obtain kernel scheduler execution authority to prepare and wait for reception of an inter-processor interruption from a processor obtaining kernel scheduler execution authority and when receiving an inter-processor interruption, set such that an exception reoccurs after thread switching by returning exception generation conditions waiting to a state before the reception of the exception.
According to the third aspect of the invention, a system which enables a plurality of processors to start execution of threads simultaneously, comprises
means for storing, with a plurality of threads to be simultaneously executed as one thread set, a context of each thread in a thread set at a context area one-to-one corresponding to a thread set provided in a context save area on a main storage, and
means for conducting exclusive arbitration during exception processing so as to temporarily allow only one processor among the plurality of processors constituting the multi-processor system to obtain kernel scheduler execution authority, wherein
a processor obtaining kernel scheduler execution authority selects a thread set to be executed next and controls such that a plurality of threads in the selected thread set are simultaneously executed at a plurality of processors including its own processor.
According to the fourth aspect of the invention, in a multi-processor system in which a plurality of threads to be simultaneously executed at a plurality of processors are stored as one thread set at a context area one-to-one corresponding to a thread set provided in a context save area on a main storage, a device which enables a plurality of processors to start execution of threads simultaneously, comprises
means for conducting exclusive arbitration during exception processing of each processor so as to temporarily allow only one processor to obtain kernel scheduler execution authority,
means for a processor obtaining kernel scheduler execution authority to save a context of a thread being executed by its own processor in the context save area on the main storage, as well as issuing a context save request as an inter-processor interruption to a processor executing other thread in the thread set to which the thread in question belongs,
means for a processor issuing a context save request to, after confirming the completion of context saving at all of the requested processors, issue a context reading request regarding a thread to be executed by other processor in a thread set to be executed next to a processor which is to execute the thread in question,
means for reading a context of a thread to be executed by its own processor in a thread set to be executed next from the context save area on the main storage to return the context,
means for a processor receiving the context reading request to read a context of a thread and return the context, and
mean for, upon completion of context return at all the processors executing threads in the thread set, enabling all the relevant processors to simultaneously start execution of threads.
In the preferred construction, the context saving request issuing means issues the context save request by designating a position in the context save area on the main storage.
In another preferred construction, the device which enables a plurality of processors to simultaneously start execution of threads in a multi-processor system further comprises means for a processor receiving an inter-processor interruption related to the context save request to save a context of a thread being executed by its own processor in a designated position of the context save area on the main storage and notify the requesting-side processor of the completion.
In another preferred construction, the context reading requesting means makes a context reading request by designating a position of the context save area on the main storage which stores a context of a thread to be executed next.
In another preferred construction, the device which enables a plurality of processors to simultaneously start execution of threads in a multi-processor system further comprises means for notifying the completion of context return to all the processors executing threads in the thread set to which the thread in question belongs.
In another preferred construction, the device which enables a plurality of processors to start execution of threads simultaneously in a multi-processor system further comprises means for enabling, at the exclusive arbitration, a processor failing to obtain kernel scheduler execution authority to prepare and wait for reception of an inter-processor interruption from a processor obtaining kernel scheduler execution authority and when receiving an inter-processor interruption, return exception generation conditions waiting to a state before the reception of the exception to set such that an exception reoccurs after thread switching.
According to another aspect of the invention, in a multi-processor system in which a plurality of threads to be simultaneously executed at a plurality of processors are stored as one thread set at a context area one-to-one corresponding to a thread set provided in a context save area on a main storage, a computer readable memory for storing a program which enables a plurality of processors to start execution of threads simultaneously,
the program comprising the steps:
(a) of conducting exclusive arbitration during exception processing of each processor so as to temporarily allow only one processor to obtain kernel scheduler execution authority,
(b) of a processor obtaining kernel scheduler execution authority to save a context of a thread being executed by its own processor in the context save area on the main storage, as well as issuing a context save request as an inter-processor interruption to a processor executing other thread in the thread set to which the thread in question belongs,
(c) of a processor issuing a context save request to, after confirming the completion of context saving at all of the requested processors, issue a context reading request regarding a thread to be executed by other processor in a thread set to be executed next to a processor which is to execute the thread in question, as well as reading a context of a thread to be executed by its own processor in the thread set to be executed next from the context save area on the main storage to return the context,
(d) of a processor receiving the context reading request to read a context of the thread to return the context, and
(e) upon completion of context return at all the processors executing threads in the thread set, of all the relevant processors to simultaneously start execution of threads.